package Demo1;

public class Partition {
    ListNode head = null;
    ListNode end = null;

    public  class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode pHead, int x) {
        ListNode sHead = null;
        ListNode sEnd = null;
        ListNode bHead = null;
        ListNode bEnd = null;

        for (; pHead != null; pHead = pHead.next){

            if (pHead.val < x){
                //小于x
                if (sHead == null){
                    sHead = pHead;
                    sEnd = pHead;
                }else{
                    sEnd.next = pHead;
                    sEnd = sEnd.next;
                }
            }else{
                //大于x
                if (bHead == null){
                    bHead = pHead;
                    bEnd = pHead;
                }else{
                    bEnd.next = pHead;
                    bEnd = bEnd.next;
                }
            }

        }



        if (sHead == null){
            return bHead;
        }

        if (bHead != null){
            bEnd.next = null;
        }

        sEnd.next = bHead;

        return sHead;
    }

/*    public ListNode partition(ListNode pHead, int x) {
        ListNode ae = null;
        ListNode as = null;
        ListNode be = null;
        ListNode bs = null;

        while (pHead != null){
            if (pHead.val < x){
                if (ae == null){
                    ae = pHead;
                    as = pHead;
                }else{
                    as.next = pHead;
                    as = as.next;
                }
            }else{
                if (be == null){
                    be = pHead;
                    bs = pHead;
                }else {
                    bs.next = pHead;
                    bs = bs.next;
                }
            }
            pHead = pHead.next;
        }

        if (ae == null){
            return be;
        }
        as.next = be;
        if (be != null){
            bs.next = null;
        }
        return ae;
    }*/


    public ListNode addFirst(int val){
        ListNode listNode = new ListNode(val);
        if (head == null){
            head = listNode;
            end = listNode;

        }else{
            end.next = listNode;
            end = listNode;
        }

        return head;
    }

}

class Main2{
    public static void main(String[] args) {
        Partition s = new Partition();
        s.addFirst(6);
        s.addFirst(2);
        Partition.ListNode ret = s.addFirst(8);
        Partition.ListNode ret2 = s.partition(ret,9);

    }
}
